package exercise;

import java.util.ArrayList;
import java.util.List;

// https://leetcode.cn/problems/triangle/
public class L230706_II {
//    Integer[][] memo;
//    public int minimumTotal(List<List<Integer>> triangle) {
//        memo = new Integer[triangle.size()][triangle.size()];
//        return dfs(triangle, 0, 0);
//    }
//
//    private int dfs(List<List<Integer>> triangle, int i, int j) {
//        if (i == triangle.size()) {
//            return 0;
//        }
//
//        if (memo[i][j] != null) {
//            return memo[i][j];
//        }
//
//        return Math.min(dfs(triangle, i+1,j), dfs(triangle, i+1, j+1)) + triangle.get(i).get(j);
//    }

    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] dp = new int[n+1];

        for (int i = n-1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[j] = Math.min(dp[j], dp[j+1]) + triangle.get(i).get(j);
            }
        }
        return dp[0];
    }

    public static void main(String[] args) {
        L230706_II s =  new L230706_II();
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> list1 = new ArrayList<>();
        list1.add(2);
        list.add(new ArrayList<>(list1));
        list1.clear();
        list1.add(3);
        list1.add(4);
        list.add(new ArrayList<>(list1));

        list1.clear();
        list1.add(6);
        list1.add(5);
        list1.add(7);
        list.add(new ArrayList<>(list1));

        list1.clear();
        list1.add(4);
        list1.add(1);
        list1.add(8);
        list1.add(3);
        list.add(new ArrayList<>(list1));

        System.out.println(s.minimumTotal(list));
    }
}
